SherbyNet - /page/wikibook/entry.mu

Micron Document

<!DOCTYPE html>

<title>Bit array</title>

</head>

Bit array

</h1>

</header>

/* start https://en.wikipedia.org/ */

.mw-parser-output .ambox{border:1px solid #a2a9b1;border-left:10px solid #36c;background-color:#fbfbfb;box-sizing:border-box}.mw-parser-output .ambox+link+.ambox,.mw-parser-output .ambox+link+style+.ambox,.mw-parser-output .ambox+link+link+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+style+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+link+.ambox{margin-top:-1px}html body.mediawiki .mw-parser-output .ambox.mbox-small-left{margin:4px 1em 4px 0;overflow:hidden;width:238px;border-collapse:collapse;font-size:88%;line-height:1.25em}.mw-parser-output .ambox-speedy{border-left:10px solid #b32424;background-color:#fee7e6}.mw-parser-output .ambox-delete{border-left:10px solid #b32424}.mw-parser-output .ambox-content{border-left:10px solid #f28500}.mw-parser-output .ambox-style{border-left:10px solid #fc3}.mw-parser-output .ambox-move{border-left:10px solid #9932cc}.mw-parser-output .ambox-protection{border-left:10px solid #a2a9b1}.mw-parser-output .ambox .mbox-text{border:none;padding:0.25em 0.5em;width:100%}.mw-parser-output .ambox .mbox-image{border:none;padding:2px 0 2px 0.5em;text-align:center}.mw-parser-output .ambox .mbox-imageright{border:none;padding:2px 0.5em 2px 0;text-align:center}.mw-parser-output .ambox .mbox-empty-cell{border:none;padding:0;width:1px}.mw-parser-output .ambox .mbox-image-div{width:52px}@media(min-width:720px){.mw-parser-output .ambox{margin:0 10%}}@media print{body.ns-0 .mw-parser-output .ambox{display:none!important}}

/* end https://en.wikipedia.org/ */

</style>

A bit array (also known as bit map, bit set, bit string, or bit vector) is an <a href="Array_data_structure" class="mw-redirect" title="Array data structure">array data structure</a> that compactly stores <a href="Bit" title="Bit">bits</a>. It can be used to implement a simple <a href="Set_data_structure" class="mw-redirect" title="Set data structure">set data structure</a>. A bit array is effective at exploiting <a href="Bit-level_parallelism" title="Bit-level parallelism">bit-level parallelism</a> in hardware to perform operations quickly. A typical bit array stores kw bits, where w is the number of bits in the unit of storage, such as a <a href="Byte" title="Byte">byte</a> or <a href="Word_(computer_architecture)" title="Word (computer architecture)">word</a>, and k is some nonnegative integer. If w does not divide the number of bits to be stored, some space is wasted due to <a href="Fragmentation_(computing)" title="Fragmentation (computing)">internal fragmentation</a>.

<div class="mw-heading mw-heading2"><h2 id="Definition">Definition</h2></div>

A bit array is a mapping from some domain (almost always a range of integers) to values in the set {0, 1}. The values can be interpreted as dark/light, absent/present, locked/unlocked, valid/invalid, et cetera. The point is that there are only two possible values, so they can be stored in one bit. As with other arrays, the access to a single bit can be managed by applying an index to the array. Assuming its size (or length) to be n bits, the array can be used to specify a subset of the domain (e.g. {0, 1, 2, ..., n−1}), where a 1-bit indicates the presence and a 0-bit the absence of a number in the set. This set data structure uses about n/w words of space, where w is the number of bits in each <a href="Word_(computer_architecture)" title="Word (computer architecture)">machine word</a>. Whether the least significant bit (of the word) or the most significant bit indicates the smallest-index number is largely irrelevant, but the former tends to be preferred (on <a href="Endianness" title="Endianness">little-endian</a> machines).

A finite <a href="Binary_relation" title="Binary relation">binary relation</a> may be represented by a bit array called a <a href="Logical_matrix" title="Logical matrix">logical matrix</a>. In the <a href="Calculus_of_relations" class="mw-redirect" title="Calculus of relations">calculus of relations</a>, these arrays are composed with <a href="Matrix_multiplication" title="Matrix multiplication">matrix multiplication</a> where the arithmetic is Boolean, and such a composition represents <a href="Composition_of_relations" title="Composition of relations">composition of relations</a>.<a href="#cite_note-1">[1]</a>

<div class="mw-heading mw-heading2"><h2 id="Basic_operations">Basic operations</h2></div>

Although most machines are not able to address individual bits in memory, nor have instructions to manipulate single bits, each bit in a word can be singled out and manipulated using <a href="Bitwise_operation" title="Bitwise operation">bitwise operations</a>. In particular:

Use <code>OR</code> to set a bit to one:

<pre> 11101010

OR 00000100

= 11101110

</pre>

<code>AND</code> to set a bit to zero:

<pre> 11101010

AND 11111101

= 11101000

</pre>

<code>AND</code> to determine if a bit is set, by zero-testing:

<pre> 11101010 11101010

AND 00000001 AND 00000010

= 00000000 = 00000010

(=0 ∴ bit isn't set) (≠0 ∴ bit is set)

</pre>

<code>XOR</code> to invert or toggle a bit:

<pre> 11101010 11101110

XOR 00000100 XOR 00000100

= 11101110 = 11101010

</pre>

<code>NOT</code> to invert all bits:

<pre>NOT 10110010

= 01001101

</pre>

To obtain the <a href="Mask_(computing)" title="Mask (computing)">bit mask</a> needed for these operations, we can use a <a href="Bitwise_operation#Bit_shifts" title="Bitwise operation">bit shift</a> operator to shift the number 1 to the left by the appropriate number of places, as well as <a href="Bitwise_negation" class="mw-redirect" title="Bitwise negation">bitwise negation</a> if necessary.

Given two bit arrays of the same size representing sets, we can compute their <a href="Union_(set_theory)" title="Union (set theory)">union</a>, <a href="Intersection_(set_theory)" title="Intersection (set theory)">intersection</a>, and <a href="Complement_(set_theory)" title="Complement (set theory)">set-theoretic difference</a> using n/w simple bit operations each (2n/w for difference), as well as the <a href="Signed_number_representations#Ones'_complement" title="Signed number representations">complement</a> of either:

<pre>for i from 0 to n/w-1

complement_a[i] := not a[i]

union[i]  := a[i] or b[i]

intersection[i] := a[i] and b[i]

difference[i]  := a[i] and (not b[i])

</pre>

If we wish to iterate through the bits of a bit array, we can do this efficiently using a doubly nested loop that loops through each word, one at a time. Only n/w memory accesses are required:

<pre>for i from 0 to n/w-1

index := 0 // if needed

word := a[i]

for b from 0 to w-1

value := word and 1 ≠ 0

word := word shift right 1

// do something with value

index := index + 1 // if needed

</pre>

Both of these code samples exhibit ideal <a href="Locality_of_reference" title="Locality of reference">locality of reference</a>, which will subsequently receive large performance boost from a data cache. If a cache line is k words, only about n/wk cache misses will occur.

<div class="mw-heading mw-heading2"><h2 id="More_complex_operations">More complex operations</h2></div>

As with <a href="String_(computer_science)" title="String (computer science)">character strings</a> it is straightforward to define length, substring, <a href="Lexicographical_order" class="mw-redirect" title="Lexicographical order">lexicographical</a> compare, concatenation, reverse operations. The implementation of some of these operations is sensitive to <a href="Endianness" title="Endianness">endianness</a>.

<div class="mw-heading mw-heading3"><h3 id="Population_/_Hamming_weight">Population / Hamming weight</h3></div>

If we wish to find the number of 1 bits in a bit array, sometimes called the population count or Hamming weight, there are efficient branch-free algorithms that can compute the number of bits in a word using a series of simple bit operations. We simply run such an algorithm on each word and keep a running total. Counting zeros is similar. See the <a href="Hamming_weight" title="Hamming weight">Hamming weight</a> article for examples of an efficient implementation.

<div class="mw-heading mw-heading3"><h3 id="Inversion">Inversion</h3></div>

Vertical flipping of a one-bit-per-pixel image, or some FFT algorithms, requires flipping the bits of individual words (so <code>b31 b30 ... b0</code> becomes <code>b0 ... b30 b31</code>).

When this operation is not available on the processor, it's still possible to proceed by successive passes, in this example on 32 bits:

<div class="mw-highlight mw-highlight-lang-text mw-content-ltr" dir="ltr"><pre>exchange two 16-bit halfwords

exchange bytes by pairs (0xddccbbaa -> 0xccddaabb)

...

swap bits by pairs

swap bits (b31 b30 ... b1 b0 -> b30 b31 ... b0 b1)

The last operation can be written ((x&0x55555555) << 1) | (x&0xaaaaaaaa) >> 1)).

</pre></div>

<div class="mw-heading mw-heading3"><h3 id="Find_first_one">Find first one</h3></div>

The <a href="Find_first_set" title="Find first set">find first set</a> or find first one operation identifies the index or position of the 1-bit with the smallest index in an array, and has widespread hardware support (for arrays not larger than a word) and efficient algorithms for its computation. When a <a href="Priority_queue" title="Priority queue">priority queue</a> is stored in a bit array, find first one can be used to identify the highest priority element in the queue. To expand a word-size find first one to longer arrays, one can find the first nonzero word and then run find first one on that word. The related operations find first zero, count leading zeros, count leading ones, count trailing zeros, count trailing ones, and log base 2 (see <a href="Find_first_set" title="Find first set">find first set</a>) can also be extended to a bit array in a straightforward manner.

<div class="mw-heading mw-heading2"><h2 id="Compression">Compression</h2></div>

A bit array is the most dense storage for "random" bits, that is, where each bit is equally likely to be 0 or 1, and each one is independent. But most data are not random, so it may be possible to store it more compactly. For example, the data of a typical fax image is not random and can be compressed. <a href="Run-length_encoding" title="Run-length encoding">Run-length encoding</a> is commonly used to compress these long streams. However, most compressed data formats are not so easy to access randomly; also by compressing bit arrays too aggressively we run the risk of losing the benefits due to bit-level parallelism (<a href="Array_programming" title="Array programming">vectorization</a>). Thus, instead of compressing bit arrays as streams of bits, we might compress them as streams of bytes or words (see <a href="Bitmap_index#Compression" title="Bitmap index">Bitmap index (compression)</a>).

<div class="mw-heading mw-heading2"><h2 id="Advantages_and_disadvantages">Advantages and disadvantages</h2></div>

Bit arrays, despite their simplicity, have a number of marked advantages over other data structures for the same problems:

<ul><li>They are extremely compact; no other data structures can store n independent pieces of data in n/w words.</li>

<li>They allow small arrays of bits to be stored and manipulated in the register set for long periods of time with no memory accesses.</li>

<li>Because of their ability to exploit bit-level parallelism, limit memory access, and maximally use the <a href="Data_cache" class="mw-redirect" title="Data cache">data cache</a>, they often outperform many other data structures on practical data sets, even those that are more asymptotically efficient.</li></ul>

However, bit arrays are not the solution to everything. In particular:

<ul><li>Without compression, they are wasteful set data structures for sparse sets (those with few elements compared to their range) in both time and space. For such applications, compressed bit arrays, <a href="Judy_array" title="Judy array">Judy arrays</a>, <a href="Trie" title="Trie">tries</a>, or even <a href="Bloom_filter" title="Bloom filter">Bloom filters</a> should be considered instead.</li>

<li>Accessing individual elements can be expensive and difficult to express in some languages. If random access is more common than sequential and the array is relatively small, a byte array may be preferable on a machine with byte addressing. A word array, however, is probably not justified due to the huge space overhead and additional cache misses it causes, unless the machine only has word addressing.</li></ul>

<div class="mw-heading mw-heading2"><h2 id="Applications">Applications</h2></div>

Because of their compactness, bit arrays have a number of applications in areas where space or efficiency is at a premium. Most commonly, they are used to represent a simple group of Boolean flags or an ordered sequence of Boolean values.

Bit arrays are used for <a href="Priority_queue" title="Priority queue">priority queues</a>, where the bit at index k is set if and only if k is in the queue; this data structure is used, for example, by the <a href="Linux_kernel" title="Linux kernel">Linux kernel</a>, and benefits strongly from a find-first-zero operation in hardware.

Bit arrays can be used for the allocation of <a href="Page_(computing)" class="mw-redirect" title="Page (computing)">memory pages</a>, <a href="Inode" title="Inode">inodes</a>, disk sectors, etc. In such cases, the term bitmap may be used. However, this term is frequently used to refer to <a href="Raster_graphics" title="Raster graphics">raster images</a>, which may use multiple <a href="Color_depth" title="Color depth">bits per pixel</a>.

Another application of bit arrays is the <a href="Bloom_filter" title="Bloom filter">Bloom filter</a>, a probabilistic <a href="Set_data_structure" class="mw-redirect" title="Set data structure">set data structure</a> that can store large sets in a small space in exchange for a small probability of error. It is also possible to build probabilistic <a href="Hash_table" title="Hash table">hash tables</a> based on bit arrays that accept either false positives or false negatives.

Bit arrays and the operations on them are also important for constructing <a href="Succinct_data_structure" title="Succinct data structure">succinct data structures</a>, which use close to the minimum possible space. In this context, operations like finding the nth 1 bit or counting the number of 1 bits up to a certain position become important.

Bit arrays are also a useful abstraction for examining streams of <a href="Data_compression" title="Data compression">compressed</a> data, which often contain elements that occupy portions of bytes or are not byte-aligned. For example, the compressed <a href="Huffman_coding" title="Huffman coding">Huffman coding</a> representation of a single 8-bit character can be anywhere from 1 to 255 bits long.

In <a href="Information_retrieval" title="Information retrieval">information retrieval</a>, bit arrays are a good representation for the posting lists of very frequent terms. If we compute the gaps between adjacent values in a list of strictly increasing integers and encode them using <a href="Unary_coding" title="Unary coding">unary coding</a>, the result is a bit array with a 1 bit in the nth position if and only if n is in the list. The implied probability of a gap of n is 1/2n. This is also the special case of <a href="Golomb_coding" title="Golomb coding">Golomb coding</a> where the parameter M is 1; this parameter is only normally selected when −log(2 − p) / log(1 − p) ≤ 1, or roughly the term occurs in at least 38% of documents.

<div class="mw-heading mw-heading2"><h2 id="Examples">Examples</h2></div>

Given a big file of <a href="IPv4" title="IPv4">IPv4</a> addresses (more than 100 GB) — we need to count unique addresses. If we use generic <code>map[string]bool</code> — we will need more than 64 GB of <a href="Random-access_memory" title="Random-access memory">RAM</a>, so lets use the bit map, in <a href="Go_(programming_language)" title="Go (programming language)">Go</a>:<div class="mw-highlight mw-highlight-lang-go mw-content-ltr mw-highlight-lines" dir="ltr"><pre>package main

import (

"bufio"

"fmt"

"math/bits"

"os"

)

// bitsetSize is the number of bytes needed for 2^32 bits (512 MiB)

const bitsetSize = 1 << 29

func main() {

file, err := os.Open("ip_addresses")

if err != nil {

fmt.Println("Error opening file:", err)

return

}

defer file.Close()

bitset := [bitsetSize]byte{}

// Use a buffered scanner with a larger buffer

scanner := bufio.NewScanner(file)

const maxBuffer = 64 * 1024 // 64 KB buffer

buf := make([]byte, 0, maxBuffer)

scanner.Buffer(buf, maxBuffer)

// Process each line

for scanner.Scan() {

line := scanner.Bytes()

// Parse the IP address manually from bytes

ip := parseIPv4(line)

// Set the bit

byteIndex := ip >> 3 // Divide by 8

bitIndex := ip & 7 // Bit position 0-7

bitset[byteIndex] |= 1 << bitIndex

}

// Check for scanning errors

if err := scanner.Err(); err != nil {

fmt.Println("Error reading file:", err)

return

}

var count uint64

for i := 0; i < bitsetSize; i++ {

count += uint64(bits.OnesCount8(bitset[i]))

}

fmt.Println("Number of unique IPv4 addresses:", count)

}

func parseIPv4(line []byte) (ip uint32) {

i := 0

// Octet 1

n := uint32(line[i] - '0')

for i = 1; line[i] != '.'; i++ {

n = n*10 + uint32(line[i]-'0')

}

ip |= n << 24

i++ // Skip the dot

// Octet 2

n = uint32(line[i] - '0')

i++

for ; line[i] != '.'; i++ {

}

i++ // Skip the dot

// Octet 3

i++

}

i++ // Skip the dot

// Octet 4

i++

for ; i < len(line); i++ {

}

ip |= n

return ip

}

</pre></div>

<div class="mw-heading mw-heading2"><h2 id="Language_support">Language support</h2></div>

The <a href="APL_(programming_language)" title="APL (programming language)">APL programming language</a> fully supports bit arrays of arbitrary shape and size as a Boolean datatype distinct from integers. All major implementations (<a href="APL_(programming_language)#Execution" title="APL (programming language)">Dyalog APL, APL2, APL Next, NARS2000, Gnu APL</a>, etc.) pack the bits densely into whatever size the machine word is. Bits may be accessed individually via the usual indexing notation (A[3]) as well as through all of the usual primitive functions and operators where they are often operated on using a special case algorithm such as summing the bits via a table lookup of bytes.

The <a href="C_(programming_language)" title="C (programming language)">C programming language</a>'s <a href="Bit_field" title="Bit field">bit fields</a>, pseudo-objects found in structs with size equal to some number of bits, are in fact small bit arrays; they are limited in that they cannot span words. Although they give a convenient syntax, the bits are still accessed using bytewise operators on most machines, and they can only be defined statically (like C's static arrays, their sizes are fixed at compile-time). It is also a common idiom for C programmers to use words as small bit arrays and access bits of them using bit operators. A widely available header file included in the <a href="X11" class="mw-redirect" title="X11">X11</a> system, xtrapbits.h, is “a portable way for systems to define bit field manipulation of arrays of bits.” A more explanatory description of aforementioned approach can be found in the <a rel="nofollow" class="external text" href="http://c-faq.com/misc/bitsets.html">comp.lang.c faq</a>.

In <a href="C%2B%2B" title="C++">C++</a>, although individual <code>bool</code>s typically occupy the same space as a byte or an integer, the <a href="Standard_Template_Library" title="Standard Template Library">STL</a> type <code>vector<bool></code> is a <a href="Partial_template_specialization" title="Partial template specialization">partial template specialization</a> in which bits are packed as a space efficiency optimization. Since bytes (and not bits) are the smallest addressable unit in C++, the [] operator does not return a reference to an element, but instead returns a <a href="Proxy_pattern" title="Proxy pattern">proxy reference</a>. This might seem a minor point, but it means that <code>vector<bool></code> is not a standard STL container, which is why the use of <code>vector<bool></code> is generally discouraged. Another unique STL class, <code>bitset</code>,<a href="#cite_note-c++-2">[2]</a> creates a vector of bits fixed at a particular size at compile-time, and in its interface and syntax more resembles the idiomatic use of words as bit sets by C programmers. It also has some additional power, such as the ability to efficiently count the number of bits that are set. The <a href="Boost_C%2B%2B_Libraries" class="mw-redirect" title="Boost C++ Libraries">Boost C++ Libraries</a> provide a <code>dynamic_bitset</code> class<a href="#cite_note-boost-3">[3]</a> whose size is specified at run-time.

The <a href="D_programming_language" class="mw-redirect" title="D programming language">D programming language</a> provides bit arrays in its standard library, Phobos, in <code>std.bitmanip</code>. As in C++, the [] operator does not return a reference, since individual bits are not directly addressable on most hardware, but instead returns a <code>bool</code>.

In <a href="Java_(programming_language)" title="Java (programming language)">Java</a>, the class <code><a rel="nofollow" class="external text" href="https://docs.oracle.com/en/java/javase/24/docs/api/java.base/java/util/BitSet.html">BitSet</a></code> creates a bit array that is then manipulated with functions named after bitwise operators familiar to C programmers. Unlike the <code>bitset</code> in C++, the Java <code>BitSet</code> does not have a "size" state (it has an effectively infinite size, initialized with 0 bits); a bit can be set or tested at any index. In addition, there is a class <code><a rel="nofollow" class="external text" href="https://docs.oracle.com/en/java/javase/24/docs/api/java.base/java/util/EnumSet.html">EnumSet</a></code>, which represents a Set of values of an <a href="Enumerated_type" title="Enumerated type">enumerated type</a> internally as a bit vector, as a safer alternative to bit fields.

The <a href=".NET_Framework" title=".NET Framework">.NET Framework</a> supplies a <code>BitArray</code> collection class. It stores bits using an array of type <code>int</code> (each element in the array usually represents 32 bits).<a href="#cite_note-4">[4]</a> The class supports random access and bitwise operators, can be iterated over, and its <code>Length</code> property can be changed to grow or truncate it.

Although <a href="Standard_ML" title="Standard ML">Standard ML</a> has no support for bit arrays, Standard ML of New Jersey has an extension, the <code>BitArray</code> structure, in its SML/NJ Library. It is not fixed in size and supports set operations and bit operations, including, unusually, shift operations.

<a href="Haskell_(programming_language)" class="mw-redirect" title="Haskell (programming language)">Haskell</a> likewise currently lacks standard support for bitwise operations, but both <a href="Glasgow_Haskell_Compiler" title="Glasgow Haskell Compiler">GHC</a> and Hugs provide a <code>Data.Bits</code> module with assorted bitwise functions and operators, including shift and rotate operations and an "unboxed" array over Boolean values may be used to model a Bit array, although this lacks support from the former module.

In <a href="Perl" title="Perl">Perl</a>, strings can be used as expandable bit arrays. They can be manipulated using the usual bitwise operators (<code>~ | & ^</code>),<a href="#cite_note-5">[5]</a> and individual bits can be tested and set using the vec function.<a href="#cite_note-6">[6]</a>

In <a href="Ruby_(programming_language)" title="Ruby (programming language)">Ruby</a>, you can access (but not set) a bit of an integer (<code>Fixnum</code> or <code>Bignum</code>) using the bracket operator (<code>[]</code>), as if it were an array of bits.

Apple's <a href="Core_Foundation" title="Core Foundation">Core Foundation</a> library contains <a rel="nofollow" class="external text" href="https://developer.apple.com/library/mac/#documentation/CoreFoundation/Reference/CFBitVectorRef/Reference/reference.html">CFBitVector</a> and <a rel="nofollow" class="external text" href="https://developer.apple.com/library/mac/#documentation/CoreFoundation/Reference/CFMutableBitVectorRef/Reference/reference.html#//apple_ref/doc/uid/20001500">CFMutableBitVector</a> structures.

<a href="PL/I" title="PL/I">PL/I</a> supports arrays of bit strings of arbitrary length, which may be either fixed-length or varying. The array elements may be aligned— each element begins on a byte or word boundary— or unaligned— elements immediately follow each other with no padding.

<a href="PL/pgSQL" title="PL/pgSQL">PL/pgSQL</a> and PostgreSQL's SQL support bit strings as native type. There are two SQL bit types: <code>bit(<code>n</code>)</code> and <code>bit varying(<code>n</code>)</code>, where <code>n</code> is a positive integer.<a href="#cite_note-7">[7]</a>

Hardware description languages such as <a href="VHDL" title="VHDL">VHDL</a>, <a href="Verilog" title="Verilog">Verilog</a>, and <a href="SystemVerilog" title="SystemVerilog">SystemVerilog</a> natively support bit vectors as these are used to model storage elements like <a href="Flip-flop_(electronics)" title="Flip-flop (electronics)">flip-flops</a>, hardware busses and hardware signals in general. In hardware verification languages such as OpenVera, <a href="E_(verification_language)" title="E (verification language)">e</a> and <a href="SystemVerilog" title="SystemVerilog">SystemVerilog</a>, bit vectors are used to sample values from the hardware models, and to represent data that is transferred to hardware during simulations.

<a href="Common_Lisp" title="Common Lisp">Common Lisp</a> provides multi-dimensional bit arrays. A one-dimensional <code>bit-vector</code> implementation is provided as a special case of the built-in <code>array</code>, acting in a dual capacity as a class and a type specifier.<a href="#cite_note-8">[8]</a> Bit arrays (and thus bit vectors) relies on the general <code>make-array</code> function to be configured with an element type of <code>bit</code>, which optionally permits a bit vector to be designated as dynamically resizable. The <code>bit-vector</code>, however, is not infinite in extent. A more restricted <code>simple-bit-vector</code> type exists, which explicitly excludes the dynamic characteristics.<a href="#cite_note-9">[9]</a> Bit vectors are represented as, and can be constructed in a more concise fashion by, the reader macro <code>#*bits</code>.<a href="#cite_note-10">[10]</a> In addition to the general functions applicable to all arrays, dedicated operations exist for bit arrays. Single bits may be accessed and modified using the <code>bit</code> and <code>sbit</code> functions<a href="#cite_note-11">[11]</a> and an extensive number of logical operations is supported.<a href="#cite_note-12">[12]</a>

<ul><li><a href="Arithmetic_logic_unit" title="Arithmetic logic unit">Arithmetic logic unit</a></li>

<li><a href="Binary_code" title="Binary code">Binary code</a></li>

<li><a href="Binary_numeral_system" class="mw-redirect" title="Binary numeral system">Binary numeral system</a></li>

<li><a href="Bitboard" title="Bitboard">Bitboard</a> Chess and similar games.</li>

<li><a href="Bit_field" title="Bit field">Bit field</a></li>

<li><a href="Bitmap_index" title="Bitmap index">Bitmap index</a></li>

<li><a href="Bitstream" title="Bitstream">Bitstream</a></li>

<li><a href="Finite_field" title="Finite field">Finite field</a> of 2 elements, or <a href="GF(2)" title="GF(2)">GF(2)</a></li>

<li><a href="Judy_array" title="Judy array">Judy array</a></li>

<li><a href="Variable-length_code" title="Variable-length code">Variable-length code</a></li></ul>

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}

/* end https://en.wikipedia.org/ */

</style><div class="reflist">

<li id="cite_note-1"><a href="#cite_ref-1">^</a> <a href="Irving_Copilowish" class="mw-redirect" title="Irving Copilowish">Irving Copilowish</a> (December 1948) "Matrix development of the calculus of relations", <a href="Journal_of_Symbolic_Logic" title="Journal of Symbolic Logic">Journal of Symbolic Logic</a> 13(4): 193–203 <a rel="nofollow" class="external text" href="https://www.jstor.org/stable/2267134?seq=1#page_scan_tab_contents">Jstor link</a>

</li>

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><cite class="citation web cs1"><a rel="nofollow" class="external text" href="http://www.sgi.com/tech/stl/bitset.html">"SGI.com Tech Archive Resources now retired"</a>. <a href="Silicon_Graphics" title="Silicon Graphics">SGI</a>. 2 January 2018.</cite>

</li>

<li id="cite_note-boost-3"><a href="#cite_ref-boost_3-0">^</a> <cite class="citation web cs1"><a rel="nofollow" class="external text" href="http://www.boost.org/libs/dynamic_bitset/dynamic_bitset.html">"dynamic_bitset<Block, Allocator> - 1.66.0"</a>. www.boost.org.</cite>

</li>

<li id="cite_note-4"><a href="#cite_ref-4">^</a> <cite class="citation web cs1"><a rel="nofollow" class="external text" href="https://github.com/microsoft/referencesource/blob/master/mscorlib/system/collections/bitarray.cs">".NET mscorlib source code"</a>. github.com/microsoft. 15 October 2021.</cite>

</li>

<li id="cite_note-5"><a href="#cite_ref-5">^</a> <cite class="citation web cs1"><a rel="nofollow" class="external text" href="http://perldoc.perl.org/perlop.html#Bitwise-String-Operators">"perlop - perldoc.perl.org"</a>. perldoc.perl.org.</cite>

</li>

<li id="cite_note-6"><a href="#cite_ref-6">^</a> <cite class="citation web cs1"><a rel="nofollow" class="external text" href="http://perldoc.perl.org/functions/vec.html">"vec - perldoc.perl.org"</a>. perldoc.perl.org.</cite>

</li>

<li id="cite_note-7"><a href="#cite_ref-7">^</a> <cite class="citation web cs1"><a rel="nofollow" class="external text" href="https://www.postgresql.org/docs/current/datatype-bit.html">"8.10. Bit String Types"</a>. 30 September 2021.</cite>

</li>

<li id="cite_note-8"><a href="#cite_ref-8">^</a> <cite class="citation web cs1"><a rel="nofollow" class="external text" href="http://www.lispworks.com/documentation/HyperSpec/Body/t_bt_vec.htm">"CLHS: System Class BIT-VECTOR"</a>. www.lispworks.com.</cite>

</li>

<li id="cite_note-9"><a href="#cite_ref-9">^</a> <cite class="citation web cs1"><a rel="nofollow" class="external text" href="http://www.lispworks.com/documentation/HyperSpec/Body/t_smp_bt.htm">"CLHS: Type SIMPLE-BIT-VECTOR"</a>. www.lispworks.com.</cite>

</li>

<li id="cite_note-10"><a href="#cite_ref-10">^</a> <cite class="citation web cs1"><a rel="nofollow" class="external text" href="http://www.lispworks.com/documentation/HyperSpec/Body/02_dhd.htm">"CLHS: Section 2.4.8.4"</a>. www.lispworks.com.</cite>

</li>

<li id="cite_note-11"><a href="#cite_ref-11">^</a> <cite class="citation web cs1"><a rel="nofollow" class="external text" href="http://www.lispworks.com/documentation/HyperSpec/Body/f_bt_sb.htm">"CLHS: Accessor BIT, SBIT"</a>. www.lispworks.com.</cite>

</li>

<li id="cite_note-12"><a href="#cite_ref-12">^</a> <cite class="citation web cs1"><a rel="nofollow" class="external text" href="http://www.lispworks.com/documentation/HyperSpec/Body/f_bt_and.htm">"CLHS: Function BIT-AND, BIT-ANDC1, BIT-ANDC2..."</a> www.lispworks.com.</cite>

</li>

</ol></div></div>

<div class="mw-heading mw-heading2"><h2 id="External_links">External links</h2></div>

<ul><li><a rel="nofollow" class="external text" href="http://www-cs-faculty.stanford.edu/~knuth/fasc1a.ps.gz">mathematical bases</a> <a rel="nofollow" class="external text" href="https://web.archive.org/web/20191016044101/http://www-cs-faculty.stanford.edu/~knuth/fasc1a.ps.gz">Archived</a> 2019-10-16 at the <a href="Wayback_Machine" title="Wayback Machine">Wayback Machine</a> by Pr. D.E.Knuth</li>

<li><a rel="nofollow" class="external text" href="http://www.gotw.ca/publications/N1185.pdf">vector<bool> Is Nonconforming, and Forces Optimization Choice</a></li>

<li><a rel="nofollow" class="external text" href="http://www.gotw.ca/publications/N1211.pdf">vector<bool>: More Problems, Better Solutions</a></li></ul>

/* start https://en.wikipedia.org/ */

.mw-parser-output .hlist dl,.mw-parser-output .hlist ol,.mw-parser-output .hlist ul{margin:0;padding:0}.mw-parser-output .hlist dd,.mw-parser-output .hlist dt,.mw-parser-output .hlist li{margin:0;display:inline}.mw-parser-output .hlist.inline,.mw-parser-output .hlist.inline dl,.mw-parser-output .hlist.inline ol,.mw-parser-output .hlist.inline ul,.mw-parser-output .hlist dl dl,.mw-parser-output .hlist dl ol,.mw-parser-output .hlist dl ul,.mw-parser-output .hlist ol dl,.mw-parser-output .hlist ol ol,.mw-parser-output .hlist ol ul,.mw-parser-output .hlist ul dl,.mw-parser-output .hlist ul ol,.mw-parser-output .hlist ul ul{display:inline}.mw-parser-output .hlist .mw-empty-li{display:none}.mw-parser-output .hlist dt::after{content:": "}.mw-parser-output .hlist dd::after,.mw-parser-output .hlist li::after{content:" · ";font-weight:bold}.mw-parser-output .hlist dd:last-child::after,.mw-parser-output .hlist dt:last-child::after,.mw-parser-output .hlist li:last-child::after{content:none}.mw-parser-output .hlist dd dd:first-child::before,.mw-parser-output .hlist dd dt:first-child::before,.mw-parser-output .hlist dd li:first-child::before,.mw-parser-output .hlist dt dd:first-child::before,.mw-parser-output .hlist dt dt:first-child::before,.mw-parser-output .hlist dt li:first-child::before,.mw-parser-output .hlist li dd:first-child::before,.mw-parser-output .hlist li dt:first-child::before,.mw-parser-output .hlist li li:first-child::before{content:" (";font-weight:normal}.mw-parser-output .hlist dd dd:last-child::after,.mw-parser-output .hlist dd dt:last-child::after,.mw-parser-output .hlist dd li:last-child::after,.mw-parser-output .hlist dt dd:last-child::after,.mw-parser-output .hlist dt dt:last-child::after,.mw-parser-output .hlist dt li:last-child::after,.mw-parser-output .hlist li dd:last-child::after,.mw-parser-output .hlist li dt:last-child::after,.mw-parser-output .hlist li li:last-child::after{content:")";font-weight:normal}.mw-parser-output .hlist ol{counter-reset:listitem}.mw-parser-output .hlist ol>li{counter-increment:listitem}.mw-parser-output .hlist ol>li::before{content:" "counter(listitem)"\a0 "}.mw-parser-output .hlist dd ol>li:first-child::before,.mw-parser-output .hlist dt ol>li:first-child::before,.mw-parser-output .hlist li ol>li:first-child::before{content:" ("counter(listitem)"\a0 "}

/* end https://en.wikipedia.org/ */

</style><style data-mw-deduplicate="TemplateStyles:r1236075235">

/* start https://en.wikipedia.org/ */

.mw-parser-output .navbox{box-sizing:border-box;border:1px solid #a2a9b1;width:100%;clear:both;font-size:88%;text-align:center;padding:1px;margin:1em auto 0}.mw-parser-output .navbox .navbox{margin-top:0}.mw-parser-output .navbox+.navbox,.mw-parser-output .navbox+.navbox-styles+.navbox{margin-top:-1px}.mw-parser-output .navbox-inner,.mw-parser-output .navbox-subgroup{width:100%}.mw-parser-output .navbox-group,.mw-parser-output .navbox-title,.mw-parser-output .navbox-abovebelow{padding:0.25em 1em;line-height:1.5em;text-align:center}.mw-parser-output .navbox-group{white-space:nowrap;text-align:right}.mw-parser-output .navbox,.mw-parser-output .navbox-subgroup{background-color:#fdfdfd}.mw-parser-output .navbox-list{line-height:1.5em;border-color:#fdfdfd}.mw-parser-output .navbox-list-with-group{text-align:left;border-left-width:2px;border-left-style:solid}.mw-parser-output tr+tr>.navbox-abovebelow,.mw-parser-output tr+tr>.navbox-group,.mw-parser-output tr+tr>.navbox-image,.mw-parser-output tr+tr>.navbox-list{border-top:2px solid #fdfdfd}.mw-parser-output .navbox-title{background-color:#ccf}.mw-parser-output .navbox-abovebelow,.mw-parser-output .navbox-group,.mw-parser-output .navbox-subgroup .navbox-title{background-color:#ddf}.mw-parser-output .navbox-subgroup .navbox-group,.mw-parser-output .navbox-subgroup .navbox-abovebelow{background-color:#e6e6ff}.mw-parser-output .navbox-even{background-color:#f7f7f7}.mw-parser-output .navbox-odd{background-color:transparent}.mw-parser-output .navbox .hlist td dl,.mw-parser-output .navbox .hlist td ol,.mw-parser-output .navbox .hlist td ul,.mw-parser-output .navbox td.hlist dl,.mw-parser-output .navbox td.hlist ol,.mw-parser-output .navbox td.hlist ul{padding:0.125em 0}.mw-parser-output .navbox .navbar{display:block;font-size:100%}.mw-parser-output .navbox-title .navbar{float:left;text-align:left;margin-right:0.5em}body.skin--responsive .mw-parser-output .navbox-image img{max-width:none!important}@media print{body.ns-0 .mw-parser-output .navbox{display:none!important}}

/* end https://en.wikipedia.org/ */

</style></div><div role="navigation" class="navbox" aria-labelledby="Data_structures216" style="padding:3px"><table class="nowraplinks hlist mw-collapsible autocollapse navbox-inner" style="border-spacing:0;background:transparent;color:inherit"><tbody><tr><th scope="col" class="navbox-title" colspan="2"><style data-mw-deduplicate="TemplateStyles:r1239400231">

/* start https://en.wikipedia.org/ */

.mw-parser-output .navbar{display:inline;font-size:88%;font-weight:normal}.mw-parser-output .navbar-collapse{float:left;text-align:left}.mw-parser-output .navbar-boxtext{word-spacing:0}.mw-parser-output .navbar ul{display:inline-block;white-space:nowrap;line-height:inherit}.mw-parser-output .navbar-brackets::before{margin-right:-0.125em;content:"[ "}.mw-parser-output .navbar-brackets::after{margin-left:-0.125em;content:" ]"}.mw-parser-output .navbar li{word-spacing:-0.125em}.mw-parser-output .navbar a>span,.mw-parser-output .navbar a>abbr{text-decoration:inherit}.mw-parser-output .navbar-mini abbr{font-variant:small-caps;border-bottom:none;text-decoration:none;cursor:inherit}.mw-parser-output .navbar-ct-full{font-size:114%;margin:0 7em}.mw-parser-output .navbar-ct-mini{font-size:114%;margin:0 4em}html.skin-theme-clientpref-night .mw-parser-output .navbar li a abbr{color:var(--color-base)!important}@media(prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .navbar li a abbr{color:var(--color-base)!important}}@media print{.mw-parser-output .navbar{display:none!important}}

/* end https://en.wikipedia.org/ */

</style><div id="Data_structures216" style="font-size:114%;margin:0 4em"><a href="Data_structure" title="Data structure">Data structures</a></div></th></tr><tr><th scope="row" class="navbox-group" style="width:1%">Types</th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Collection_(abstract_data_type)" title="Collection (abstract data type)">Collection</a></li>

<li><a href="Container_(abstract_data_type)" title="Container (abstract data type)">Container</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Abstract_data_type" title="Abstract data type">Abstract</a></th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Associative_array" title="Associative array">Associative array</a>

<ul><li><a href="Multimap" title="Multimap">Multimap</a></li>

<li><a href="Retrieval_Data_Structure" title="Retrieval Data Structure">Retrieval Data Structure</a></li></ul></li>

<li><a href="Stack_(abstract_data_type)" title="Stack (abstract data type)">Stack</a></li>

<li><a href="Queue_(abstract_data_type)" title="Queue (abstract data type)">Queue</a>

<ul><li><a href="Double-ended_queue" title="Double-ended queue">Double-ended queue</a></li></ul></li>

<li><a href="Priority_queue" title="Priority queue">Priority queue</a>

<ul><li><a href="Double-ended_priority_queue" title="Double-ended priority queue">Double-ended priority queue</a></li></ul></li>

<ul><li><a href="Set_(abstract_data_type)#Multiset" title="Set (abstract data type)">Multiset</a></li>

<li><a href="Disjoint-set_data_structure" title="Disjoint-set data structure">Disjoint-set</a></li></ul></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Array_(data_structure)" title="Array (data structure)">Arrays</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul>

<li><a href="Circular_buffer" title="Circular buffer">Circular buffer</a></li>

<li><a href="Dynamic_array" title="Dynamic array">Dynamic array</a></li>

<li><a href="Hash_table" title="Hash table">Hash table</a></li>

<li><a href="Hashed_array_tree" title="Hashed array tree">Hashed array tree</a></li>

<li><a href="Sparse_matrix" title="Sparse matrix">Sparse matrix</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Linked_data_structure" title="Linked data structure">Linked</a></th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Association_list" title="Association list">Association list</a></li>

<li><a href="Linked_list" title="Linked list">Linked list</a></li>

<li><a href="Unrolled_linked_list" title="Unrolled linked list">Unrolled linked list</a></li>

<li><a href="XOR_linked_list" title="XOR linked list">XOR linked list</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Tree_(data_structure)" class="mw-redirect" title="Tree (data structure)">Trees</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">

<li><a href="Binary_search_tree" title="Binary search tree">Binary search tree</a>

<li><a href="Red%E2%80%93black_tree" title="Red–black tree">Red–black tree</a></li>

<li><a href="Self-balancing_binary_search_tree" title="Self-balancing binary search tree">Self-balancing tree</a></li>

<li><a href="Splay_tree" title="Splay tree">Splay tree</a></li></ul></li>

<ul><li><a href="Binary_heap" title="Binary heap">Binary heap</a></li>

<li><a href="Binomial_heap" title="Binomial heap">Binomial heap</a></li>

<li><a href="Fibonacci_heap" title="Fibonacci heap">Fibonacci heap</a></li></ul></li>

<li><a href="Hilbert_R-tree" title="Hilbert R-tree">Hilbert R-tree</a></li></ul></li>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Graph_(abstract_data_type)" title="Graph (abstract data type)">Graphs</a></th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Binary_decision_diagram" title="Binary decision diagram">Binary decision diagram</a></li>

<li><a href="Directed_acyclic_graph" title="Directed acyclic graph">Directed acyclic graph</a></li>

<li><a href="Deterministic_acyclic_finite_state_automaton" title="Deterministic acyclic finite state automaton">Directed acyclic word graph</a></li></ul>

</div></td></tr><tr><td class="navbox-abovebelow" colspan="2"><div>

<ul><li><a href="List_of_data_structures" title="List of data structures">List of data structures</a></li></ul>

</div></td></tr></tbody></table></div></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2025-07-10" href="https://en.wikipedia.org/wiki/?title=Bit_array&oldid=1299738559">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>